package July.BinSerach;

public class BinSearch {

public static void main(String[] args) {
    Solution s = new Solution();
    int[] a = new int[]{4,5,6,7,0,1,2};
    s.search(a, 0);
}    
    
}


//剑指 Offer 11. 旋转数组的最小数字

//近似的折半查找
class Solution001 {
    public int minArray(int[] numbers) {
        int low = 0;
        int high = numbers.length-1;
        int mid ;
        while(low<=high){
            mid = low+(high-low)/2;//防止溢出
            //如果中间比右边小,那么右边就是完全有序的,最小值可能为中间
            if(numbers[mid]<numbers[high]) high=mid;
            //如果中间比右边大,那么最小值肯定在两个中间
            else if(numbers[mid]>numbers[high]) low=mid+1;
            //如果两个值相等,没办法判断,只能--,期待值不同的时候进行mid的定位
            else high--;
        }
        return numbers[low];
    }
}

//版本2
//33. 搜索旋转排序数组

//旋转后的数组找指定值
class Solution {


    //five解法
//     private int minArray(int[] numbers) {
        
//         int low = 0;
//         int high = numbers.length-1;
//         int mid ;
//         while(low<=high){
//             mid = low+(high-low)/2;//防止溢出
//             //如果中间比右边小,那么右边就是完全有序的,最小值可能为中间
//             if(numbers[mid]<numbers[high]) high=mid;
//             //如果中间比右边大,那么最小值肯定在两个中间
//             else if(numbers[mid]>numbers[high]) low=mid+1;
//             //如果两个值相等,没办法判断,只能--,期待值不同的时候进行mid的定位
//             else high--;
//         }
//         return low;
//     }

//     public int search(int[] nums, int target) {
//         if(numbers.length==0) return -1;
//         int minIndex = minArray(nums);
//         int low = 0;
//         int high = nums.length-1;
//         if(target>nums[nums.length-1]){
//             high = minIndex;
//         }
//         if(nums[0]>target){
//             low = minIndex;
//         }
//         int mid;
//         while(low<=high){
//             mid = low +(high-low)/2;
//             if(nums[mid]==target) return mid;
//             else if(nums[mid]<target) low = mid+1; 
//             else high= mid-1;
//         }
//         return -1;
//    }



public int search(int[] nums, int target) {

    int n = nums.length;
    int l =0;
    int r = n-1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) return mid;
        if (nums[0] <= nums[mid]) {
            if (nums[0] <= target && target < nums[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[n - 1]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }
    return -1;
}
}